Many communications systems, for example, Global Navigation Satellite System (GNSS) use spread spectrum communication signals. Spread-spectrum communication systems use a synchronized version of a spreading code to demodulate the received signal. Such systems often require a process for reducing or removing Doppler frequency shift. A Doppler frequency shift is the change in apparent frequency of a source of electromagnetic radiation when there is a relative motion between the signal source and the receiver that is attempting to synchronize with a spread-spectrum communications system.
For example, GNSS receivers generate a local signal within the receiver that matches the carrier frequency, and, optionally, the phase, of the incoming signal. The two signals, the local and incoming, are then effectively multiplied together to effect carrier removal. If the frequency of the local signal matches that of the incoming signal's apparent carrier frequency, the result of the Doppler removal process contains no carrier frequency component and consists entirely of the ranging code. This signal is then multiplied by time-shifted versions of the local replica of the ranging code. This process is known as correlation. The term “Doppler removal” is used herein to describe the carrier removal process that accounts for the combination of the nominal incoming carrier frequency, and possibly any or all Doppler frequency shifts.
For software-based GNSS receivers, the Doppler removal and correlation process is computationally very expensive. Conventional Doppler removal is effected for each Satellite being tracked (i.e. Doppler removal is performed on a satellite-by-satellite basis).
Basic GNSS Receiver Operation
FIG. 1 illustrates a GNSS receiver as known in the prior art. Receiver 100, as shown in FIG. 1, includes an antenna 105 that receives GNSS communication signals from multiple satellites (not shown). The signals are down-converted to a lower intermediate frequency (IF) by the RF front end 110. This lower frequency signal (IF signal) is then sampled at a rate of fs by the analog to digital converter (ADC) 115. The output samples, herein referred to as IF samples, can be real-valued or in quadraphase (I and Q).
The IF samples are then passed to up to multiple tracking channels shown for example as tracking channels 1-Z, where Z is defined by the number of satellites currently in view, or the maximum number of channels that can be accommodated by the receiver. The measurements output from the tracking channels are passed to a navigator 120 that can compute the position and/or the velocity of the antenna.
FIG. 2 illustrates a functional block diagram of a basic tracking channel in accordance with the prior art. Tracking channel 200, shown in FIG. 2, includes a Doppler removal module 205 that receives the IF samples from the ADC 115. The IF samples are multiplied by the sine and cosine of a locally generated carrier phase signal that is generated by the Carrier Numerically Controlled Oscillator (NCO) 210. The output from the Doppler removal module is passed to one or more correlators 215. Each correlator 215 multiplies the samples from the Doppler removal module 205 by a locally generated version of the ranging code, generated by a coder driven by the code NCO 220 and accumulates the results over some predefined time interval. The processor 225 performs multiple tasks including determining the error in the locally generated carrier and code and providing correction signals to the respective NCOs.
Received Signal as Seen by Tracking Channels
The IF samples output from the ADC 115 of FIG. 1 contain a superposition of signals from all satellites in view of the antenna. However, since each tracking channel is responsible for tracking the signal of a given satellite, and because GNSS systems are inherently designed to minimize problems introduced by receiving signals from multiple satellites simultaneously, the discussion can be simplified to consider only one satellite's signal at a time. With this in mind, the incoming signal is assumed to have a center frequency of fIF Hz and thus the quadraphase samples can then be expressed asIk=Ak·Ck·Dk·cos(2πfIFTsk+φ)  (1)Qk=Ak·Ck·Dk·sin(2πfIFTsk+φ)  (2)
where the subscript k refers to the epoch; A is the signal amplitude; C is the ranging code; D is the navigation data bit; Ts=fs−1 is the sample period; and φ is the phase. It is also noted that the center frequency also contains Doppler shifts introduced by receiver motion, satellite motion and any time varying range errors due, for example, to atmospheric effects. For real-valued IF samples, the corresponding equation is the same as equation (1). The following sections describe the traditional methods of Doppler removal and code correlation.
Doppler Removal
Doppler removal has traditionally been done in one of two ways. The first method uses a rigorously generated local carrier. The second method uses a lookup table of locally generated signals at a limited number of frequencies.
Rigorous Method
The signals in equations (1) and (2) are first rotated as follows
                                                                        I                k                a                            =                                                                    I                    k                                    ·                                      cos                    ⁡                                          (                                                                        2                          ⁢                          π                          ⁢                                                      f                            ^                                                    ⁢                                                      T                            s                                                    ⁢                          k                                                +                                                  φ                          ^                                                                    )                                                                      +                                                                            Q                      k                                        ·                    sin                                    ⁢                                                                          ⁢                                      (                                                                  2                        ⁢                        π                        ⁢                                                  f                          ^                                                ⁢                                                  T                          s                                                ⁢                        k                                            +                                              φ                        ^                                                              )                                                                                                                          =                                                A                  k                                ·                                  C                  k                                ·                                  D                  k                                ·                                  {                                                                                                                                          cos                            ⁢                                                                                                                  ⁢                                                                                          (                                                                                                      2                                    ⁢                                    π                                    ⁢                                                                                                                                                  ⁢                                                                          f                                      IF                                                                        ⁢                                                                          T                                      s                                                                        ⁢                                    k                                                                    +                                  φ                                                                )                                                            ·                              cos                                                        ⁢                                                                                                                  ⁢                                                          (                                                                                                2                                  ⁢                                  π                                  ⁢                                                                                                                                          ⁢                                                                      f                                    ^                                                                    ⁢                                                                      T                                    s                                                                    ⁢                                  k                                                                +                                                                  φ                                  ^                                                                                            )                                                                                +                                                                                                                                                              sin                          ⁢                                                                                                          ⁢                                                                                    (                                                                                                2                                  ⁢                                  π                                  ⁢                                                                                                                                          ⁢                                                                      f                                    IF                                                                    ⁢                                                                      T                                    s                                                                    ⁢                                  k                                                                +                                φ                                                            )                                                        ·                            sin                                                    ⁢                                                                                                          ⁢                                                      (                                                                                          2                                ⁢                                π                                ⁢                                                                                                                                  ⁢                                                                  f                                  ^                                                                ⁢                                                                  T                                  s                                                                ⁢                                k                                                            +                                                              φ                                ^                                                                                      )                                                                                                                                }                                                                                                        =                                                                    A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                  cos                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                                              (                                                                              f                            IF                                                    -                                                      f                            ^                                                                          )                                            ⁢                                              T                        s                                            ⁢                      k                                        +                                          (                                              φ                        -                                                  φ                          ^                                                                    )                                                        )                                                                                                        =                                                                    A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                  cos                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                      δ                      ⁢                                                                                          ⁢                                              fT                        s                                            ⁢                      k                                        +                    δφ                                    )                                                                                        (        3        )                                                                                    Q                k                a                            =                                                                    -                                          I                      k                                                        ·                                      sin                    ⁡                                          (                                                                        2                          ⁢                          π                          ⁢                                                      f                            ^                                                    ⁢                                                      T                            s                                                    ⁢                          k                                                +                                                  φ                          ^                                                                    )                                                                      +                                                                            Q                      k                                        ·                    cos                                    ⁢                                                                          ⁢                                      (                                                                  2                        ⁢                        π                        ⁢                                                  f                          ^                                                ⁢                                                  T                          s                                                ⁢                        k                                            +                                              φ                        ^                                                              )                                                                                                                          =                                                A                  k                                ·                                  C                  k                                ·                                  D                  k                                ·                                  {                                                                                                                                                                        -                              cos                                                        ⁢                                                                                                                  ⁢                                                                                          (                                                                                                      2                                    ⁢                                    π                                    ⁢                                                                                                                                                  ⁢                                                                          f                                      IF                                                                        ⁢                                                                          T                                      s                                                                        ⁢                                    k                                                                    +                                  φ                                                                )                                                            ·                              sin                                                        ⁢                                                                                                                  ⁢                                                          (                                                                                                2                                  ⁢                                  π                                  ⁢                                                                                                                                          ⁢                                                                      f                                    ^                                                                    ⁢                                                                      T                                    s                                                                    ⁢                                  k                                                                +                                                                  φ                                  ^                                                                                            )                                                                                +                                                                                                                                                              sin                          ⁢                                                                                                          ⁢                                                                                    (                                                                                                2                                  ⁢                                  π                                  ⁢                                                                                                                                          ⁢                                                                      f                                    IF                                                                    ⁢                                                                      T                                    s                                                                    ⁢                                  k                                                                +                                φ                                                            )                                                        ·                            cos                                                    ⁢                                                                                                          ⁢                                                      (                                                                                          2                                ⁢                                π                                ⁢                                                                                                                                  ⁢                                                                  f                                  ^                                                                ⁢                                                                  T                                  s                                                                ⁢                                k                                                            +                                                              φ                                ^                                                                                      )                                                                                                                                }                                                                                                        =                                                                    A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                  sin                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                                              (                                                                              f                            IF                                                    -                                                      f                            ^                                                                          )                                            ⁢                                              T                        s                                            ⁢                      k                                        +                                          (                                              φ                        -                                                  φ                          ^                                                                    )                                                        )                                                                                                        =                                                                    A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                  sin                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                      δ                      ⁢                                                                                          ⁢                                              fT                        s                                            ⁢                      k                                        +                    δφ                                    )                                                                                        (        4        )            
where {circumflex over (f)}(=fIF−δf) and {circumflex over (φ)} are the locally generated frequency and phase; and δf and δφ are their respective (tracking) errors. As can seen, if the frequency is perfectly replicated, the resulting signal contains no frequency components, since δφ is constant. Equations (3) and (4) represent the output of the Doppler removal process.
For real-valued IF samples, the Doppler removal process is accomplished using
                                                                        I                k                a                            =                            ⁢                                                                    I                    k                                    ·                  2                  ·                  cos                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                              f                        ^                                            ⁢                                              T                        s                                            ⁢                      k                                        +                                          φ                      ^                                                        )                                                                                                        =                            ⁢                                                                    A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                  2                  ·                  cos                                ⁢                                                                  ⁢                                                      (                                                                  2                        ⁢                        π                        ⁢                                                                                                  ⁢                                                  f                          IF                                                ⁢                                                  T                          s                                                ⁢                        k                                            +                      φ                                        )                                    ·                  cos                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                              f                        ^                                            ⁢                                              T                        s                                            ⁢                      k                                        +                                          φ                      ^                                                        )                                                                                                        =                            ⁢                                                                                          A                      k                                        ·                                          C                      k                                        ·                                          D                      k                                        ·                    cos                                    ⁢                                                                          ⁢                                      (                                                                  2                        ⁢                        πδ                        ⁢                                                                                                  ⁢                                                  fT                          s                                                ⁢                        k                                            +                      δφ                                        )                                                  +                                                      A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                                                                                                                      ⁢                              sin                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                                              (                                                                              f                            IF                                                    +                                                      f                            ^                                                                          )                                            ⁢                                              T                        s                                            ⁢                      k                                        +                    δφ                                    )                                                                                        (        5        )                                                                                    Q                k                a                            =                            ⁢                                                                    I                    k                                    ·                  2                  ·                  sin                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                              f                        ^                                            ⁢                                              T                        s                                            ⁢                      k                                        +                                          φ                      ^                                                        )                                                                                                        =                            ⁢                                                                    A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                  2                  ·                  cos                                ⁢                                                                  ⁢                                                      (                                                                  2                        ⁢                        π                        ⁢                                                                                                  ⁢                                                  f                          IF                                                ⁢                                                  T                          s                                                ⁢                        k                                            +                      φ                                        )                                    ·                  sin                                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                              f                        ^                                            ⁢                                              T                        s                                            ⁢                      k                                        +                                          φ                      ^                                                        )                                                                                                        =                            ⁢                                                                                          A                      k                                        ·                                          C                      k                                        ·                                          D                      k                                        ·                    sin                                    ⁢                                                                          ⁢                                      (                                                                  2                        ⁢                        πδ                        ⁢                                                                                                  ⁢                                                  fT                          s                                                ⁢                        k                                            +                      δφ                                        )                                                  +                                                      A                    k                                    ·                                      C                    k                                    ·                                      D                    k                                    ·                                                                                                                      ⁢                              cos                ⁢                                                                  ⁢                                  (                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                                              (                                                                              f                            IF                                                    +                                                      f                            ^                                                                          )                                            ⁢                                              T                        s                                            ⁢                      k                                        +                    δφ                                    )                                                                                        (        6        )            
The above results are equivalent to the quadraphase case, but with one additional term in each equation. It is worth noting that this extra term has approximately twice the frequency of the original IF signal (since the locally generated signal is expected to closely match the IF signal). The influence of these terms will be minimized through a subsequent correlation process and thus no serious degradation in system performance is realized.
Table Method
The Table Method employs a lookup table of locally generated signals at a limited number of frequencies instead of generating the local carrier at the desired Doppler (which can be computationally expensive). Using the Table Method, the sine and cosine of signals of various frequencies is stored such that they need not be recomputed. In this case, the frequency error term (δf) in equations (3) and (4) contains not only the tracking error, but also an error due to having limited frequency resolution. Mathematically, the locally generated frequency can be written as{circumflex over (f)}=fIF−δf−δfT 
where δfT is the error introduced by using a quantized frequency. As such, the final forms of equations (3) and (4) can be rewritten asIka=Ak·Ck·Dk·cos(2πδfTsk+2πδfTTsk+δφ)  (7)Qka=Ak·Ck·Dk·sin(2πδfTsk+2πδfTTsk+δφ)  (8)Correlation
The correlation process is performed as follows
                              I          b                =                              ∑                          k              =              1                        N                    ⁢                                                    C                ^                            k                        ·                          I              k              a                                                          (        9        )                                          Q          b                =                              ∑                          k              =              1                        N                    ⁢                                                    C                ^                            k                        ·                          Q              k              a                                                          (        10        )            
where Ĉk is the locally generated code; and N is the number of samples. If the summation is performed during the same data bit, the Dk term can be ignored. Assuming the Doppler removal was done using the rigorous method, equations (9) and (10) can be approximated by
                              I          b                ≈                              A            ·            R                    ⁢                                          ⁢                                    (              δτ              )                        ·                                          sin                ⁢                                                                  ⁢                                  (                                      πδ                    ⁢                                                                                  ⁢                                          fT                      s                                        ⁢                    N                                    )                                                            π                ⁢                                                                  ⁢                δ                ⁢                                                                  ⁢                f                ⁢                                                                  ⁢                                  T                  s                                                      ·            cos                    ⁢                                          ⁢                      (                                          π                ⁢                                                                  ⁢                δ                ⁢                                                                  ⁢                f                ⁢                                                                  ⁢                                  T                  s                                ⁢                N                            +              δφ                        )                                              (        11        )                                          Q          b                ≈                              A            ·            R                    ⁢                                          ⁢                                    (              δτ              )                        ·                                          sin                ⁢                                                                  ⁢                                  (                                      πδ                    ⁢                                                                                  ⁢                                          fT                      s                                        ⁢                    N                                    )                                                            π                ⁢                                                                  ⁢                δ                ⁢                                                                  ⁢                f                ⁢                                                                  ⁢                                  T                  s                                                      ·            sin                    ⁢                                          ⁢                      (                                          π                ⁢                                                                  ⁢                δ                ⁢                                                                  ⁢                f                ⁢                                                                  ⁢                                  T                  s                                ⁢                N                            +              δφ                        )                                              (        12        )            
where R(δτ) is the ranging code auto-correlation function with an error in the locally generated code of δτ. Similarly, if the table method was used, the approximations are as follows
                              I          b                ≈                              A            ·            R                    ⁢                                          ⁢                                    (              δτ              )                        ·                                          sin                ⁢                                                                  ⁢                                  (                                      π                    ⁢                                                                                  ⁢                                          (                                                                        δ                          ⁢                                                                                                          ⁢                          f                                                +                                                  δ                          ⁢                                                                                                          ⁢                                                      f                            T                                                                                              )                                        ⁢                                          T                      s                                        ⁢                    N                                    )                                                            π                ⁢                                                                  ⁢                                  (                                                            δ                      ⁢                                                                                          ⁢                      f                                        +                                          δ                      ⁢                                                                                          ⁢                                              f                        T                                                                              )                                ⁢                                  T                  s                                                      ·            cos                    ⁢                                          ⁢                      (                                          π                ⁢                                                                  ⁢                δ                ⁢                                                                  ⁢                f                ⁢                                                                  ⁢                                  T                  s                                ⁢                N                            +                              πδ                ⁢                                                                  ⁢                                  f                  T                                ⁢                                  T                  s                                ⁢                N                            +              δφ                        )                                              (        13        )                                          Q          b                ≈                              A            ·            R                    ⁢                                          ⁢                                    (              δτ              )                        ·                                          sin                ⁢                                                                  ⁢                                  (                                      π                    ⁢                                                                                  ⁢                                          (                                                                        δ                          ⁢                                                                                                          ⁢                          f                                                +                                                  δ                          ⁢                                                                                                          ⁢                                                      f                            T                                                                                              )                                        ⁢                                          T                      s                                        ⁢                    N                                    )                                                            π                ⁢                                                                  ⁢                                  (                                                            δ                      ⁢                                                                                          ⁢                      f                                        +                                          δ                      ⁢                                                                                          ⁢                                              f                        T                                                                              )                                ⁢                                  T                  s                                                      ·            sin                    ⁢                                          ⁢                      (                                          π                ⁢                                                                  ⁢                δ                ⁢                                                                  ⁢                f                ⁢                                                                  ⁢                                  T                  s                                ⁢                N                            +                              πδ                ⁢                                                                  ⁢                                  f                  T                                ⁢                                  T                  s                                ⁢                N                            +              δφ                        )                                              (        14        )            
However, since δfT is known (recall it is the difference between the frequency in the table and the frequency that was intended to be generated) the above values can be rotated (by πδfTTsN) as follows
                                                                                          I                  ~                                b                            =                                                                                          I                      b                                        ·                    cos                                    ⁢                                                                          ⁢                                      (                                          πδ                      ⁢                                                                                          ⁢                                              f                        T                                            ⁢                                              T                        s                                            ⁢                      N                                        )                                                  +                                                                            Q                      b                                        ·                    sin                                    ⁢                                                                          ⁢                                      (                                          π                      ⁢                                                                                          ⁢                      δ                      ⁢                                                                                          ⁢                                              f                        T                                            ⁢                                              T                        s                                            ⁢                      N                                        )                                                                                                                          =                                                A                  ·                  R                                ⁢                                                                  ⁢                                                      (                                          δ                      ⁢                                                                                          ⁢                      τ                                        )                                    ·                                                            sin                      ⁢                                                                                          ⁢                                              (                                                  π                          ⁢                                                                                                          ⁢                                                      (                                                                                          δ                                ⁢                                                                                                                                  ⁢                                f                                                            +                                                              δ                                ⁢                                                                                                                                  ⁢                                                                  f                                  T                                                                                                                      )                                                    ⁢                                                      T                            s                                                    ⁢                          N                                                )                                                                                    π                      ⁢                                                                                          ⁢                                              (                                                                              δ                            ⁢                                                                                                                  ⁢                            f                                                    +                                                      δ                            ⁢                                                                                                                  ⁢                                                          f                              T                                                                                                      )                                            ⁢                                              T                        s                                                                              ·                  cos                                ⁢                                                                  ⁢                                  (                                                            πδ                      ⁢                                                                                          ⁢                                              fT                        s                                            ⁢                      N                                        +                    δφ                                    )                                                                                        (        15        )                                                                                                      Q                  ~                                b                            =                                                                                          -                                              I                        b                                                              ·                    sin                                    ⁢                                                                          ⁢                                      (                                          πδ                      ⁢                                                                                          ⁢                                              f                        T                                            ⁢                                              T                        s                                            ⁢                      N                                        )                                                  +                                                                            Q                      b                                        ·                    cos                                    ⁢                                                                          ⁢                                      (                                          π                      ⁢                                                                                          ⁢                      δ                      ⁢                                                                                          ⁢                                              f                        T                                            ⁢                                              T                        s                                            ⁢                      N                                        )                                                                                                                          =                                                A                  ·                  R                                ⁢                                                                  ⁢                                                      (                                          δ                      ⁢                                                                                          ⁢                      τ                                        )                                    ·                                                            sin                      ⁢                                                                                          ⁢                                              (                                                  π                          ⁢                                                                                                          ⁢                                                      (                                                                                          δ                                ⁢                                                                                                                                  ⁢                                f                                                            +                                                              δ                                ⁢                                                                                                                                  ⁢                                                                  f                                  T                                                                                                                      )                                                    ⁢                                                      T                            s                                                    ⁢                          N                                                )                                                                                    π                      ⁢                                                                                          ⁢                                              (                                                                              δ                            ⁢                                                                                                                  ⁢                            f                                                    +                                                      δ                            ⁢                                                                                                                  ⁢                                                          f                              T                                                                                                      )                                            ⁢                                              T                        s                                                                              ·                  sin                                ⁢                                                                  ⁢                                  (                                                            πδ                      ⁢                                                                                          ⁢                                              fT                        s                                            ⁢                      N                                        +                    δφ                                    )                                                                                        (        16        )            
Comparing equations (15) and (16) with (11) and (12), the only difference is in the quotient term. Since this term acts as an attenuating factor that decreases (in magnitude) with total frequency error and/or integration time (TsN), the table method will typically have slightly more attenuation than the rigorous method. This is because, generally speaking, frequency error due to frequency quantization will be non-zero. However, if the frequency quantization is small enough, the extra attenuation can be considered negligible.
The attenuation factor discussed above is also the reason that when using real-valued IF samples, the additional terms in equations (5) and (6) have minimal influence on overall performance. Specifically, since the large frequency “error” in these terms (which is approximately twice the IF frequency) will have a correspondingly small (in magnitude) attenuation factor.
As a final note, the rotation performed in equations (15) and (16) should also account for the fact that the stored frequency tables generally start at zero phase but that during any given accumulation time interval, the locally generated phase will generally not start with zero phase.
Computational Complexity
It is useful to quantify the computational aspects of the traditional algorithms. The focus here will be on the table method since this method is computationally more efficient with only negligible disadvantages (if implemented properly). To quantify the computational complexity, only multiplications and additions are considered. Computation of the transcendental functions is not included in this calculation since in the table method these values are computed once and read from the lookup table.
Referring to the top line of equations (3) and (4), the Doppler removal process requires 4N multiplications and 2N additions. From equations (9) and (10), the correlation process requires 2N multiplications and 2N additions. However, for the table method, an additional four multiplications and two additions are needed for the rotation in equations (15) and (16). The total number of computations required for tracking K satellites using L correlators is summarized in Table 1.
TABLE 1Number of Computations Required For Table MethodDoppler Removal and Correlation (Assuming K Satellitesand L Correlators per Satellite)ProcessMultiplicationsAdditionsDoppler Removal4NK2NKCorrelation(2N + 4)KL(2N + 2)KLAs a final note, for real-valued IF samples Table 1 remains virtually unchanged except that there are only 2NK multiplications and NK additions required for the Doppler removal process.